Supporting a seamless map in peer-to-peer system for massively multiplayer online role playing games

摘要

Massively Multiplayer Online Role Playing Games feature huge maps that can be partitioned into smaller components called zones to achieve scalability. In peer-to-peer (P2P) systems, those zones can be assigned to peers who are willing to take up the role of zone servers. A seamless map requires inter-zone communications to allow interactions between players across zone boundaries. In assigning zones to peers, it is critical to seek approaches to reduce the inter-zone communication cost in P2P system. In this paper, we formulate the zone assignment problem for P2P system and demonstrate that the problem is NP-hard. We hence propose a low-cost heuristic that partitions the physical network into bins, as well as, aggregating the partitions of the virtual world by clustering neighboring zones in a game map. We then demonstrate that by assigning clustered neighboring zones in the virtual map into peers in common physical network bins, we are able to achieve similar inter-zone communication cost for the zone assignment problem as that can be achieved by the optimization model we formulated, while avoiding the prohibitively high computation cost required by the latter.